package com.tgy.algorithm.base._数组和;

public class _正数数组和小于等于 {


    public static int integerLtEq(int[] nums, int k) {

        if (nums == null || nums.length == 0) {
            return 0;
        }

        int len = nums.length;

        int[] minValues = new int[len];
        int[] minValueIndexs = new int[len];

        minValues[len - 1] = nums[len - 1];
        minValueIndexs[len - 1] = len - 1;

        for (int i = len - 2; i >= 0; i--) {
            if (minValues[i + 1] <= 0) {
                minValues[i] = minValues[i+1] + nums[i];
                minValueIndexs[i] = minValueIndexs[i+1];
            }else {
                minValues[i] = nums[i];
                minValueIndexs[i] = i;
            }
        }


        int leftIndex = 0;
        int rightIndex = 0;
        int maxLen = 0;
        int sum = 0;
        while (leftIndex < len) {
//            leftIndex = rightIndex;
            while (rightIndex < len && sum + minValues[rightIndex] <= k) {
                sum += minValues[rightIndex];
                rightIndex = (minValueIndexs[rightIndex] + 1);
            }

            maxLen = Math.max(maxLen, rightIndex - leftIndex);
            if (leftIndex < rightIndex) {
                sum -= nums[leftIndex];
                leftIndex++;
            }else {
                sum = 0;
                rightIndex++;
                leftIndex++;
            }
        }

        return maxLen;
    }


    public static void main(String[] args) {
        int[] nums = new int[]{2,1,-2,3,-1,3,2};
        int maxLen = integerLtEq(nums, 2);
        System.out.println(maxLen);
    }
}
